package bin_tree;

public class MyBinTree {
    private static class TreeNode{//创建内部类
        char val;
        //左子树根节点
        TreeNode left;
        //右子树根节点
        TreeNode right;
        public TreeNode(char val){
            this.val=val;
        }
    }

    /**
     * 创建一个二叉树，返回根节点
     * @return
     */
    public static TreeNode build(){
        TreeNode nodeA=new TreeNode('A');
        TreeNode nodeB=new TreeNode('B');
        TreeNode nodeC=new TreeNode('C');
        TreeNode nodeD=new TreeNode('D');
        TreeNode nodeE=new TreeNode('E');
        TreeNode nodeF=new TreeNode('F');
        TreeNode nodeG=new TreeNode('G');
        TreeNode nodeH=new TreeNode('H');
        nodeA.left=nodeB;
        nodeA.right=nodeC;
        nodeB.left=nodeD;
        nodeB.right=nodeE;
        nodeE.right=nodeH;
        nodeC.left=nodeF;
        nodeC.right=nodeG;
        return nodeA;
    }
    /**
     * 先序
     */
    public static void preOrder(TreeNode root){
        //边界条件-判空
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public static void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        preOrder(root.left);
        System.out.print(root.val+" ");
        preOrder(root.right);
    }
    public static void postOrder(TreeNode root){
        if(root==null){
            return;
        }
        preOrder(root.left);
        preOrder(root.right);
        System.out.print(root.val+" ");
    }
    public static void main(String[] args) {
        TreeNode root=build();
        System.out.println("前序遍历的结果为：");
        preOrder(root);
        System.out.println();
        System.out.println("中序遍历结果为：");
        inOrder(root);
        System.out.println();
        System.out.println("后序遍历结果为：");
        postOrder(root);
    }
    public static int getNodes(TreeNode root){
        //统计二叉树节点个数
        if(root==null){
            return 0;
        }
        return 1+getNodes(root.left)+getNodes(root.right);
    }
    public static int getLeafNodes(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodes(root.right)+getLeafNodes(root.right);
    }
    public static boolean contains(TreeNode root,char val){
        if (root==null){
            return false;
        }
        if(root.val==val){
            return true;
        }
        //二叉树不为空且根节点值不是val，在子树中继续寻找
        return contains(root.left,val)||contains(root.right,val);
    }
    public static int height(TreeNode root){
        if(root==null){
            return 0;
        }
        //有根节点
        return 1+Math.max(height(root.left),height(root.right));
    }
    public static int getKLevelNodes(TreeNode root,int k){
        if(root==null||k<=0){
            return 0;
        }
        if(k==1){
            return 1;
        }
        //二叉树不为空且k>=2
        return getKLevelNodes(root.left,k-1)+getKLevelNodes(root.right,k-1);
    }
}
